"""
算法思想：又称 "缩小增量排序"，通过设定增量d将数组分为若干子序列，对每个子序列进行直接插入排序；逐次缩小增量d（通常取d = d//2），直至d=1，最后进行一次直接插入排序。
代码解释：
初始增量d设为n//2，后续每次缩小为d//2，直至d=1。
对每个增量d，数组被分为d个子序列（索引i, i+d, i+2d,...为一个子序列）。
对每个子序列应用直接插入排序逻辑，仅将比较和移动的步长改为d。
最后当d=1时，整个数组进行一次直接插入排序，保证最终有序。
时间复杂度与增量选择有关，平均情况约为O(n^1.3)。
"""


def shell_sort(arr):
    n = len(arr)
    # 初始增量设为数组长度的一半
    d = n // 2

    # 当增量d >= 1时，继续排序
    while d >= 1:
        # 对每个子序列进行直接插入排序
        # i从d开始，保证每个子序列都被处理
        for i in range(d, n):
            key = arr[i]  # 保存当前待插入元素
            j = i - d  # 指向同子序列中前一个元素

            # 在子序列中找到插入位置
            while j >= 0 and key < arr[j]:
                arr[j + d] = arr[j]  # 元素后移d位
                j -= d

            # 插入元素
            arr[j + d] = key

        # 缩小增量
        d = d // 2

    return arr


# 测试
arr = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10]
sorted_arr = shell_sort(arr)
print("希尔排序结果:", sorted_arr)
# 输出: [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]
